1343E - Weights Distributing - CodeForces Solution

#include <climits>
#include <iostream>
#include <cmath>
#include <algorithm> 
#include <vector>
#include <numeric>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for (int i = a; i < b; ++i)
#define MAXN 200002
int p[MAXN], dist[3][MAXN];
ll pre[MAXN];
vi adj[MAXN];
void bfs(int s, int i, int n) {
  fill_n(dist[i], n, -1);
  queue<int> q;
  q.push(s);
  dist[i][s] = 0;
  while(!q.empty()) {
    int cur = q.front();q.pop();
    for(auto k : adj[cur]) {
      if(dist[i][k] != -1) continue;
      dist[i][k] = dist[i][cur] + 1;
      q.push(k);
    }
  }
}
void solve() {
  int n,m,a,b,c; cin>>n>>m>>a>>b>>c;a--;b--;c--;
  REP(i, 0, m) cin>>p[i];
  REP(i,0,n) adj[i].clear();
  sort(p, p + m);
  pre[0] = p[0];
  REP(i, 1, m) pre[i] = pre[i-1] + p[i];
  REP(i,0,m) {
    int u,v;cin>>u>>v;u--;v--;adj[u].push_back(v);adj[v].push_back(u);
  }
  bfs(a,0,n);
  bfs(b,1,n);
  bfs(c,2,n);
  ll ans = LLONG_MAX;
  for(int y = 0; y < n; ++y) {
    int ay = dist[0][y], by = dist[1][y], cy = dist[2][y];
    //cout << "a: " << a << " b: " << b << " c: "<< c << " y: "<<y<< " ay: "<<ay <<" by: "<<by<< " cy: " << cy << endl;
    if(ay+by+cy > m) continue;
    ans = min(ans, pre[by-1] + pre[ay+by+cy-1]);
  }
  cout << ans << "\n";
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0),cout.sync_with_stdio(0);
  int T; cin>>T;
  while(T--) {
    solve();
  }
  return 0;
}